package org.rcgwt.client.ui.grid.internal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.rcgwt.client.ui.grid.IIndexList;
import org.rcgwt.client.ui.grid.internal.js.IntSet;

/**
 * 
 * @author Matthieu & Olivier Oeuillot
 * @version $Revision: $ $Date: $
 */
public class IntRangeList implements Cloneable, IIndexList {

    private static final int[] EMPTY_INT_ARRAY = new int[0];

    public static final IntRangeList EMPTY_RANGE_LIST = new IntRangeList() {
        {
            readOnly = true;
        }

        @Override
        public IntRangeList intersects(IntRange range) {
            return this;
        }

        @Override
        public IntRangeList intersects(IntRangeList interval) {
            return this;
        }

        @Override
        public boolean isEmpty() {
            return true;
        }

        @Override
        public int size() {
            return 0;
        }

        @Override
        public boolean contains(int index) {
            return false;
        }

        @Override
        public boolean contains(IntRange interval) {
            return false;
        }

        @Override
        public IntIterator iterator() {
            return IntRange.EMPTY_INT_ITERATOR;
        }

    };

    protected final List<IntRange> ranges = new ArrayList<IntRange>(1);

    protected boolean readOnly = false;

    public IntRangeList() {
    }

    public IntRangeList(int startIndex, int count) {
        this();

        addInterval(startIndex, count);
    }

    public IntRangeList(int... indexes) {
        this();

        compactIndexes(this, indexes, 0, indexes.length);
    }

    public IntRangeList(int indexes[], int start, int length) {
        this();

        compactIndexes(this, indexes, start, length);
    }

    protected static void compactIndexes(IntRangeList intRangeList,
            int indexes[], int start, int length) {

        if (length == 0) {
            return;
        }
        if (length == 1) {
            intRangeList.addIndex(indexes[0]);
            return;
        }

        // TODO algo ne marche pas avec length=1

        int exclusiveEnd = start + length;

        Arrays.sort(indexes, start, exclusiveEnd);

        int last = indexes[start];
        int lastIndex = 0;
        int i = start + 1;
        for (; i < exclusiveEnd; i++) {
            int cur = indexes[i];

            if (cur == last || cur == last + 1) {
                last = cur;
                continue;
            }

            intRangeList.addInterval(indexes[lastIndex], indexes[i - 1]
                    - indexes[lastIndex] + 1);

            lastIndex = i;
            last = cur;
        }

        if (lastIndex < i - 1) {
            intRangeList.addInterval(indexes[lastIndex], indexes[i - 1]
                    - indexes[lastIndex] + 1);
        }
    }

    public void addIndexes(int indexes[]) {
        if (readOnly) {
            throw new IllegalStateException("Can not change intRangeList");
        }

        compactIndexes(this, indexes, 0, indexes.length);
    }

    public IntRange addIndex(int index) {
        if (readOnly) {
            throw new IllegalStateException("Can not change intRangeList");
        }

        // //Check if already exists
        for (int i = 0; i < ranges.size(); i++) {
            IntRange range = ranges.get(i);
            if (range.contains(index)) {
                return range;
            }

            // Contigue inferieur
            if (index == range.getFirstIndex() - 1) {
                range.setStartIndex(index);
                return range;
            }

            // Contigue superieur
            if (index == range.getLastIndex() + 1) {
                range.setLastIndex(index);
                return range;
            }

            if (index < range.getFirstIndex()) {
                IntRange newrange = new IntRange(index, 1);
                ranges.add(i, newrange);
                return newrange;
            }
        }

        IntRange newrange = new IntRange(index, 1);
        ranges.add(newrange);
        return newrange;
    }

    public IntRange addInterval(int startIndex, int count) {
        return addInterval(new IntRange(startIndex, count));
    }

    public IntRange addInterval(IntRange newRange) {
        if (readOnly) {
            throw new IllegalStateException("Can not change intRangeList");
        }

        int indexstop = newRange.getFirstIndex() + newRange.size();
        for (int i = 0; i < ranges.size(); i++) {
            IntRange range = ranges.get(i);
            if (range.contains(newRange)) {
                return range;
            }

            // Contigue inferieur
            if ((newRange.getFirstIndex() < range.getFirstIndex())
                    && (indexstop > range.getFirstIndex())) {
                range.setStartIndex(newRange.getFirstIndex());

                if (indexstop > range.getFirstIndex() + range.size()) {
                    range.setCount(indexstop - range.getFirstIndex());
                }
                // TODO Check Union
                return range;
            }
        }

        ranges.add(newRange);
        Collections.sort(ranges);
        merge();
        return newRange;

    }

    public void addInterval(IntRangeList interval) {
        Iterator<IntRange> iter = interval.ranges.iterator();
        while (iter.hasNext()) {
            IntRange intRange = iter.next();
            addInterval(intRange);
        }

    }

    public boolean contains(int index) {
        Iterator<IntRange> iter = ranges.iterator();
        while (iter.hasNext()) {
            IntRange intRange = iter.next();
            if (intRange.contains(index)) {
                return true;
            }
        }
        return false;
    }

    public boolean contains(IntRange interval) {
        Iterator<IntRange> iter = ranges.iterator();
        while (iter.hasNext()) {
            IntRange intRange = iter.next();
            if (intRange.contains(interval)) {
                return true;
            }
        }
        return false;
    }

    public IntRangeList intersects(IntRange range) {
        IntRangeList intersect = null;
        Iterator<IntRange> iter = ranges.iterator();

        while (iter.hasNext()) {
            IntRange intRange = iter.next();

            IntRange inter = intRange.intersect(range);
            if (inter == null) {
                continue;
            }

            if (intersect == null) {
                intersect = new IntRangeList();
            }
            intersect.addInterval(inter);
        }

        if (intersect == null) {
            return EMPTY_RANGE_LIST;
        }

        return intersect;
    }

    public IntRangeList intersects(IntRangeList interval) {
        IntRangeList intersect = null;

        for (IntRange range : interval.ranges) {

            IntRangeList intersectedList = this.intersects(range);
            if (intersectedList.isEmpty()) {
                continue;
            }

            if (intersect == null) {
                intersect = new IntRangeList();
            }

            intersect.addInterval(intersectedList);
        }

        if (intersect == null) {
            return EMPTY_RANGE_LIST;
        }

        return intersect;
    }

    public IntIterator iterator() {
        return new IntIteratorDefault(this);
    }

    private static class IntIteratorDefault implements IntIterator {

        private int rangeIndex = 0;

        private IntIterator iterInt;

        private IntRangeList list;

        public IntIteratorDefault(IntRangeList list) {
            this.list = list;

        }

        public int next() {
            return iterInt.next();
        }

        public boolean hasNext() {
            if (iterInt == null) {
                if (list.ranges.size() > 0) {
                    rangeIndex = 0;
                    iterInt = list.ranges.get(rangeIndex).iterator();
                    return hasNext();
                }

                return false;
            }

            if (iterInt.hasNext()) {
                return true;
            }

            rangeIndex++;
            if (rangeIndex < list.ranges.size()) {
                iterInt = list.ranges.get(rangeIndex).iterator();
                return hasNext();
            }

            return false;
        }
    }

    public boolean remove(int index) {
        Iterator<IntRange> iter = ranges.iterator();

        while (iter.hasNext()) {
            IntRange range = iter.next();
            if (range.contains(index) == false) {
                continue;
            }

            if (range.getFirstIndex() == index) {
                range.setStartIndex(index + 1);
                range.setCount(range.size() - 1);

            } else if (range.getFirstIndex() + range.size() - 1 == index) {
                range.setCount(range.size() - 1);

            } else {
                // Creation de range
                IntRange beforeRange = new IntRange(range.getFirstIndex(),
                        index);
                IntRange afterRange = new IntRange(index + 1, range.size()
                        - index - 1);
                ranges.remove(range);
                ranges.add(beforeRange);
                ranges.add(afterRange);
                Collections.sort(ranges);
            }

            return true;
        }
        return false;
    }

    public boolean remove(IntRange range) {

        // Range={2,3,4} rangeCurrent{2,3,4} => {}
        if (ranges.contains(range)) {
            return ranges.remove(range);
        }

        Iterator<IntRange> iter = ranges.iterator();
        int indexstop = range.getLastIndex();
        while (iter.hasNext()) {
            IntRange rangeCurrent = iter.next();
            // Range={2,3,4} rangeCurrent{2,3,4} => {}
            if (rangeCurrent.equals(range)) {
                return ranges.remove(range);
            }

            // rangeCurrent{2,3}- Range={4,5} => {2,3}
            if (rangeCurrent.getLastIndex() < range.getFirstIndex()) {
                continue;
            }
            if (rangeCurrent.getFirstIndex() > range.getLastIndex()) {
                continue;
            }
            if (range.getLastIndex() < rangeCurrent.getFirstIndex()) {
                continue;
            }
            if (range.getFirstIndex() > rangeCurrent.getLastIndex()) {
                continue;
            }

            // rangeCurrent{2,3,4}- Range={1,2} => {3,4}
            if (range.getFirstIndex() < rangeCurrent.getFirstIndex()
                    && (indexstop < rangeCurrent.getLastIndex())) {
                // Le range à supprimer recoupe le début, suppression du début
                // rangeCurrent.setCount(rangeCurrent.getStartIndex()
                // + rangeCurrent.getCount() - indexstop);
                rangeCurrent.setStartIndex(indexstop + 1);

                return true;
            }

            // rangeCurrent={2,3,4} Range={2} => {3,4}
            if (range.getFirstIndex() == rangeCurrent.getFirstIndex()) {
                if (range.getLastIndex() >= rangeCurrent.getLastIndex()) {
                    iter.remove();
                    continue;
                }

                rangeCurrent.setStartIndex(range.getLastIndex() + 1);
                continue;
            }

            // rangeCurrent{2,3,4} - Range={3} => {2}{4}
            if ((range.getFirstIndex() > rangeCurrent.getFirstIndex())
                    && range.getLastIndex() < rangeCurrent.getLastIndex()) {

                // Le range est compris dans l'autre
                IntRange afterRange = IntRange.createIntRange(rangeCurrent
                        .getFirstIndex(), range.getFirstIndex() - 1);
                ranges.add(afterRange);
                rangeCurrent.setStartIndex(range.getLastIndex() + 1);
                Collections.sort(ranges);

                return true;
            }

            // rangeCurrent{2,3,4}- Range={4,5} => {2,3}
            if ((range.getFirstIndex() > rangeCurrent.getFirstIndex())
                    && (range.getFirstIndex() <= rangeCurrent.getLastIndex())) {

                rangeCurrent.setLastIndex(range.getFirstIndex() - 1);

                continue;
            }

            // rangeCurrent{2,3,4}- Range={1,2,3,4,5} => {}
            if ((range.getFirstIndex() <= rangeCurrent.getFirstIndex())
                    && (range.getLastIndex() >= rangeCurrent.getLastIndex())) {

                iter.remove();

                continue;
            }
        }

        return false;
    }

    public void remove(IntRangeList rangeList) {

        for (IntRange range : rangeList.ranges) {
            remove(range);
        }

    }

    public void removeAll() {
        ranges.clear();
    }

    public boolean isEmpty() {
        return ranges.isEmpty();
    }

    public static void IntRangeHelper(IntRangeList rangeList, int[] list) {

        if (list == null) {
            return;
        }

        Arrays.sort(list);

        if (rangeList == null) {
            rangeList = new IntRangeList();
        }

        IntRange range = null;
        for (int i = 0; i < list.length; i++) {
            if (range == null) {
                range = new IntRange(list[i], 1);
                continue;
            }

            if (range.getLastIndex() + 1 == list[i]) {
                // C'est contigue, on allonge le range
                range.setCount(range.size() + 1);
                continue;
            }

            // On ajoute le range à la liste (avec check)
            rangeList.addInterval(range);
            // On crée le nouveau range
            range = new IntRange(list[i], 1);
        }

        if (range != null) { // Pour ne pas oublier le dernier élément
            // On ajoute le range à la liste (avec check)
            rangeList.addInterval(range);
        }

    }

    public int size() {
        int res = 0;
        for (IntRange range : ranges) {
            res += range.size();
        }
        return res;
    }

    public int[] toArray() {

        IntSet set = null;

        for (IntRange range : ranges) {
            if (set == null) {
                set = new IntSet(range.toArray());

            } else {
                set.add(range.toArray());
            }
        }

        if (set != null) {
            return set.toArray();
        }

        return EMPTY_INT_ARRAY;
    }

    @Override
    public String toString() {

        return ranges.toString();
    }

    @Override
    public boolean equals(Object obj) {
        // TODO A refaire ....
        if (obj instanceof IntRangeList) {
            return Arrays.equals(((IntRangeList) obj).toArray(), toArray());
        }

        return false;
    }

    public IntRangeList clone() {
        IntRangeList clone = new IntRangeList();

        for (IntRange range : ranges) {
            clone.addInterval(range.clone());
        }

        return clone;
    }

    public int getFirstIndex() {
        if (ranges.isEmpty()) {
            return -1;
        }

        return ranges.get(0).getFirstIndex();
    }

    public int getLastIndex() {
        if (ranges.isEmpty()) {
            return -1;
        }

        return ranges.get(ranges.size() - 1).getLastIndex();
    }

    private void merge() {
        IntRange previousRange = null;

        for (int i = 0; i < ranges.size();) {
            IntRange currentRange = ranges.get(i);
            if (previousRange != null) {
                if (previousRange.getLastIndex() == currentRange
                        .getFirstIndex() - 1) {
                    previousRange.setLastIndex(currentRange.getLastIndex());
                    ranges.remove(i);
                    continue;
                }
            }
            previousRange = currentRange;
            i++;
        }
    }
}
